package 数据结构.章节10;

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;

/**
 * @author 挚爱之夕
 * @date 2021/10/25 - 10 - 25 - 17:09
 * @Description: 数据结构.章节10
 * @Version: 1.0
 */
public class _171_布尔过滤器 {
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter();
        ArrayList<String> contents = new ArrayList<>();
        contents.add("sldkjelsjf");
        contents.add("ggl;ker;gekr");
        contents.add("wieoneamfwe");
        contents.add("sldekfjiaif");
        contents.add("ksldkfjlajfl");
        for (int i = 0; i < contents.size(); i++) {
            bf.addElement(contents.get(i));
        }
        System.out.println(bf.check("1"));
        System.out.println(bf.check("sldkjelsjf"));
        System.out.println(bf.check("ggl;ker;gekr"));
    }


    private static class BloomFilter{
        //位图的长度
        public static final int NUM_SLOTS = 1024*1024*8;
        //hash函数的个数，一个hash函数的结果用于标记一个位
        public static final int NUM_HASH = 8;
        //位图
        private BigInteger bitmap = new BigInteger("0");

        //hash:将message+n映射到0~NUM_SLOTS-1
        private int hash(String message,int n){
            message = message + String.valueOf(n);
            try{
                //将任意输入映射成128位(16个字节)整数的hash函数
                MessageDigest md5 = MessageDigest.getInstance("md5");
                byte[] bytes = message.getBytes();
                md5.update(bytes);
                byte[] digest = md5.digest();
                //获得message+n的md5结果(128位整数)
                BigInteger bi = new BigInteger(digest);

                return Math.abs(bi.intValue())%NUM_SLOTS;
            }catch (NoSuchAlgorithmException ex){
                System.out.println("error");
            }
            return -1;
        }
        public void addElement(String message){
            for (int i = 0; i < NUM_HASH; i++) {
                //代表hash1、hash2...hash8
                //结果用于标注位图的该位为1
                int hashcode = hash(message,i);
                if(!bitmap.testBit(hashcode)){//如果还不为1
                    //标记位图的该位为1
                    bitmap = bitmap.or(new BigInteger("1").shiftLeft(hashcode));
                }
            }
        }
        public boolean check(String message){
            for (int i = 0; i < NUM_HASH; i++) {
                int hashcode = hash(message,i);
                //该位不为1,元素不存在
                if(!bitmap.testBit(hashcode)){
                    return false;
                }
            }
            return true;
        }
    }
}
